﻿using System.Collections.Generic;
using Xunit;
using Xunit.Abstractions;

namespace 初级算法.其他
{
    public class 删除链表的倒数第N个节点
    {
        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int val = 0, ListNode next = null)
            {
                this.val = val;
                this.next = next;
            }
        }
        public class Solution
        {
            /// <summary>
            /// len-n+1
            /// https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
            /// 执行用时：80 ms, 在所有 C# 提交中击败了100.00%的用户
            /// 内存消耗：24.7 MB, 在所有 C# 提交中击败了56.08%的用户
            /// </summary>
            /// <param name="head"></param>
            /// <param name="n"></param>
            /// <returns></returns>
            public ListNode RemoveNthFromEnd(ListNode head, int n)
            {
                int len = GetLength(head);

                ListNode dummy = new ListNode(0, head);

                ListNode currentNode = dummy;

                int i = 1;
                while (i < len - n + 1)
                {
                    currentNode = currentNode.next;
                    i++;
                }

                currentNode.next = currentNode.next.next;

                return dummy.next;
            }

            public int GetLength(ListNode node)
            {
                int len = 0;
                while (node != null)
                {
                    len++;
                    node = node.next;
                }
                return len;
            }
        }
        ITestOutputHelper output;

        public 删除链表的倒数第N个节点(ITestOutputHelper output)
        {
            this.output = output;
        }

        [Fact]
        public void Test1()
        {

            Solution S = new Solution();
            ListNode n, r;
            //n = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
            //r = S.RemoveNthFromEnd(n,2);
            //Print(r);

            n = new ListNode(1, new ListNode(2));
            r = S.RemoveNthFromEnd(n, 2);
            Print(r);


            output.WriteLine("");

            n = new ListNode(1, new ListNode(2));
            r = S.RemoveNthFromEnd(n, 1);
            Print(r);
        }


        private void Print(ListNode n)
        {
            output.WriteLine("" + n.val);
            if (n.next == null) return;
            Print(n.next);
        }
    }
}
